Thuật từ "nhà nước cảnh sát" được dùng lần đầu tiên vào năm 1851 để ám chỉ việc sử dụng lực lượng cảnh sát quốc gia duy trì trật tự tại Áo.[4] Từ tiếng Đức này (Polizeistaat) bắt đầu được dùng phổ biến trong tiếng Anh vào thập niên 1930 khi đề cập tới các chính phủ toàn trị mà bắt đầu xuất hiện ở Âu Châu.[5]

Thật sự, ngay ở cấp địa phương, việc sử dụng một lực lượng cảnh sát để tích cực duy trì trật tự, không kể các tình trạng khẩn cấp, thì gần như chưa được biết đến trước thời gian đó.

Thí dụ, việc sử dụng lần đầu tiên một lực lượng cảnh sát tiểu bang tại Hoa Kỳ đã xảy ra trong khoảng thời gian rất gần đó là vào năm 1865 khi một lực lượng như thế được thành lập tại tiểu bang Massachusetts.[6]

Cho đến thời điểm này, trật tự tại đa số các nơi được duy trì ở cấp bậc địa phương với chút ít sự trợ giúp từ cảnh sát quận khi được yêu cầu trong một số sự cố nào đó. Khi việc duy trì một lực lượng cảnh sát thường trực trở nên phổ biến hơn vào cuối thế kỷ 19 và đầu thế kỷ 20 thì thuật từ "nhà nước cảnh sát" được dùng rộng rải hơn để ám chỉ đến các quốc gia nào sử dụng lực lượng lớn cảnh sát theo chiều hướng có tính chất trấn áp và mạnh tay, thí dụ như dưới chế độ phát-xít, cộng sản, hay được áp dụng mở rộng đến những sự kiện lịch sử có tính chất đàn áp như Cách mạng Pháp và Đế quốc La Mã.[7][8]

Bởi vì có những quan điểm chính trị khác nhau về mức độ cân bằng thích hợp giữa tự do cá nhân và an ninh quốc gia, không có tiêu chuẩn khách quan để xác định việc thuật ngữ "nhà nước cảnh sát" có thể được áp dụng với một quốc gia cụ thể hay không. Bất kỳ một quốc gia nào cũng duy trì lực lượng cảnh sát và các biện pháp giám sát công dân (dù ít hay nhiều) để đảm bảo an ninh chung cho đất nước. Vì vậy, rất khó để đánh giá một cách khách quan về những lời cáo buộc rằng một quốc gia có hay không là một nhà nước cảnh sát. Một cách để xem xét các khái niệm về nhà nước cảnh sát và trạng thái tự do là thông qua sự trung gian giữa các giai đoạn: luật pháp hạn chế bớt tự do cá nhân được coi là tiến tới một nhà nước cảnh sát, trong khi luật pháp hạn chế bớt sự giám sát của chính phủ thì được coi là hướng tới chính sách tự do[9].